package com.desheng.bigdata.ds.map;

import java.util.Iterator;

/**
 * @Description 自定义双列符号表，模拟hashmap，采用数组+链表
 *          注意：本类中并没有实现扩容，下一步将实现扩容和遍历
 * @Author deshenglijun
 * @Date 2020/5/17 21:00
 * @Version 1.0
 */
public class MyHashMap<K, V> {
    private final int DEFAULT_INIT = 10;
    private int size;

    private Node<K, V>[] elements;
    //负载因子
    private double loadFactor = 0.75;

    private class Node<K, V> {
        K key;
        V value;
        int hash;
        Node<K, V> next;

        public Node(int hash, K key, V value, Node<K, V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

    //hashcode值
    private int hash(K key){
        return Math.abs(key.hashCode());
    }
    public MyHashMap() {
        this.elements = new Node[DEFAULT_INIT];
        this.size = 0;
    }

    public MyHashMap(int initSize) {
        this.elements = new Node[initSize];
        this.size = 0;
    }

    public int size() {
        return this.size;
    }

    public boolean isEmpty() {
        return this.size == 0;
    }

    public void put(K key, V value) {
        int h = hash(key);
        int index = h & (elements.length - 1);
        Node<K, V> p = elements[index];
        if(p == null) {
            elements[index] = new Node<>(h, key, value, null);
        } else {
            Node<K, V> i = p;
            for(; i.next != null; i = i.next) {
                if(i.key.equals(key)) {
                    i.value = value;
                    return;
                }
            }
            i.next = new Node<>(h, key, value, null);
        }
        size++;
    }

    public V get(K key) {
        int index = hash(key) & (elements.length - 1);
        Node<K, V> p = elements[index];
        if(p == null) {
            return null;
        } else {
            Node<K, V> i = p;
            for(; i.next != null; i = i.next) {
                if(i.key.equals(key)) {
                    return i.value;
                }
            }
        }
        return null;
    }

    public V delete(K key) {
        int index = hash(key) & (elements.length - 1);
        Node<K, V> p = elements[index];
        if(p == null) {
            return null;
        } else {
            Node<K, V> pre = p;
            Node<K, V> cur = pre.next;
            if(pre.key.equals(key)) {
                elements[index] = cur;
                size--;
                return pre.value;
            }
            for(; cur.next != null; pre = cur, cur = cur.next) {
                if(cur.key.equals(key)) {
                    V oldValue = cur.value;
                    pre.next = cur.next;
                    size--;
                    return oldValue;
                }
            }
        }
        return null;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        for(Node<K, V> node : elements) {
            for (; node != null; node = node.next) {
                sb.append(node.key + "=" + node.value);
                sb.append(", ");
            }
        }
        return sb.substring(0, sb.lastIndexOf(",")) + "]";
    }

}
